package 递归回溯;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.List;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-26
 **/

public class 面试题08_06汉诺塔问题 {

    /**
     * 在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，
     * 盘子可以滑入任意一根柱子。一开始，
     * 所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
     * (1) 每次只能移动一个盘子;
     * (2) 盘子只能从柱子顶端滑出移到下一根柱子;
     * (3) 盘子只能叠在比它大的盘子上。
     * <p>
     * 请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
     * 你需要原地修改栈。
     * <p>
     * 示例1:
     * 输入：A = [2, 1, 0], B = [], C = []
     * 输出：C = [2, 1, 0]
     * 示例2:
     * 输入：A = [1, 0], B = [], C = []
     * 输出：C = [1, 0]
     * <p>
     * 提示:
     * A中盘子的数目不大于14个。
     */

    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {

        /**
         * 需要(n-1)个先移动到B,再将最后一个移动到C
         * 然后将(n-2)个先移动到A,再将最后一个移动到C
         */
        this.dfs(A.size(), A, B, C);
    }

    private void dfs(int num, List<Integer> source, List<Integer> mid, List<Integer> target) {
        if (num == 1) {
            target.add(source.remove(source.size() - 1));
            return;
        }

        // 第一(n-1)个盘子移动到第二  B是目标盘
        this.dfs(num - 1, source, target, mid);
        // 移动A最后一个盘子到C上 (每次都移动最后一个盘子,所以是size - 1)
        target.add(source.remove(source.size() - 1));
        // 继续反着来,将B上的(n-1)个盘子移动到A
        this.dfs(num - 1, mid, source, target);

    }

    public static void main(String[] args) {
        面试题08_06汉诺塔问题 n = new 面试题08_06汉诺塔问题();
        List<Integer> list = new ArrayList<>();
        list.add(2);
        list.add(1);
        list.add(0);
        ArrayList<Integer> c = new ArrayList<>();
        n.hanota(
                list,
                new ArrayList<>(),
                c);
        System.out.println(JSON.toJSONString(c));
    }

}
